package com.work.jike;

/**
 * 34-35.二分查找求平方根.对应leetcode第69题
 * Created by suk on 2020/8/23.
 */
public class Sqrt_34_69 {
    public static void main(String[] args) {
        System.out.println(mySqrt(10));
    }

    public static int mySqrt(int x) {
        int l = 0;
        int r = x;
        int result = 0;

        if (x == 1 || x == 0) {
            return x;
        }
        // x = 8
        while (l <= r) {
            int mid = (l + r) / 2;
            /**
             * 防止超过int的上限,故改为除法
             */
            if (mid == x / mid) {
                return mid;
            } else if (mid > x / mid) { // 注意这个判断不能写反
                r = mid - 1;
                result = r;
            } else {
                l = mid + 1;

            }
        }
        return result;

    }

    public int binarySort(int[] arrays, int target) {
        int left = 0;
        int right = arrays.length;
        int result = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (arrays[mid] == target) {
                return mid;
            } else if (arrays[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
                result = mid;
            }

        }
        return result;
    }

}
